const boardElem = document.getElementById('board_elem');
const n_rows_control = document.getElementById('n_rows_control');
const n_cols_control = document.getElementById('n_cols_control');
const btn_random = document.getElementById('btn_random');
const btn_replay = document.getElementById('btn_replay');
const btn_solve = document.getElementById('btn_solve');
const gameHeader = document.getElementById('game_header');
const difficulty_control = document.getElementById('difficulty_control');
const btn_next = document.getElementById('btn_next');
const btn_play = document.getElementById('btn_play');

let n_rows,n_cols;

if (localStorage.config && localStorage.config !== '{}') {
    let config = JSON.parse(localStorage.config);
    n_rows_control.value = n_rows = config.n_rows;
    n_cols_control.value = n_cols = config.n_cols;
} else {
    n_rows_control.value = n_rows = 4;
    n_cols_control.value = n_cols = 0;
}


let where = [];
let board = [];
let mat = [];
let auto = false;

let font_size;

const directions = [[0, 1], [0, -1], [-1, 0], [1, 0]];

window.addEventListener('beforeunload', () => {
    localStorage.config = JSON.stringify({n_rows, n_cols})
})

function random_mat(num) {  // 按一定的步数进行滑动打乱
    mat = [];
    for (let i = 0; i < n_rows; i++) {
        let row = [];
        for (let j = 0; j < n_cols; j++)
            row.push(i * n_cols + j + 1);
        mat.push(row);
    }
    mat[n_rows - 1][n_cols - 1] = 0;
    // console.log(JSON.stringify(mat));
    init_pos();
    for (let i = 0; i < num; i++) {
        while (true) {
            let [dr, dc] = directions[Math.floor(Math.random() * 4)];
            // console.log(dr, dc);
            let [r, c] = [where[0][0] + dr, where[0][1] + dc];
            if (r >= 0 && r < n_rows && c >= 0 && c < n_cols) {
                slide(mat, where, dr, dc);
                // console.log(JSON.stringify(mat));
                break;
            }
        }
    }
}


function completely_random_board() {  // 完全随机，但最后会检验是否有解并调整
    let len = n_rows * n_cols - 1;
    const numbers = Array.from({length: len}, (_, index) => index + 1);
    let inv_flag = false;  // 逆序数奇偶性，偶数为false

    // Fisher-Yates shuffle算法
    for (let i = len - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));  // j 有 i+1 个可能取值情况
        [numbers[i], numbers[j]] = [numbers[j], numbers[i]];
        if (i !== j)
            inv_flag = !inv_flag;
    }
    const index = Math.floor(Math.random() * len);
    numbers.splice(index, 0, 0);  // 插入空格

    // 检测是否可解，若不可解则随机交换两个滑块
    if (!solvable(numbers, inv_flag)) {
        let i = 1 + Math.floor(Math.random() * (len - 1));
        let j = Math.floor(Math.random() * i);
        if (i >= index) i++;
        if (j >= index) j++;
        [numbers[i], numbers[j]] = [numbers[j], numbers[i]];
    }
    return numbers;
}


function strToMatrix(str) {

}

function solvable(arr, inv) {
    let space_row = Math.floor(arr.indexOf(0) / n_cols);  // 空格所在行号
    if (n_cols % 2 === 1)  // 列数为奇数
        return inv % 2 === 0;
    // 列数为偶数
    return (inv + n_rows - 1 - space_row) % 2 === 0;
}


function inv_count() {
    let inv = 0  // 逆序数
    for (let i = 0; i < board.length - 1; i++)
        if (board[i] !== 0)
            for (let j = i + 1; j < board.length; j++)
                if (board[i] > board[j] && board[j] !== 0)
                    inv++;
    return inv;
}


function draw() {
    // 清空board_elem所有子元素
    while (boardElem.firstChild)
        boardElem.removeChild(boardElem.firstChild);
    font_size = 140 / Math.max(n_rows, n_cols);
    font_size = Math.max(font_size, 15);
    document.documentElement.style.setProperty('--cell-font-size', font_size + 'px');

    for (let i = 0; i < n_rows; i++) {
        let tr = document.createElement('tr');
        for (let j = 0; j < n_cols; j++) {
            let td = document.createElement('td');
            td.dataset.row = String(i);
            td.dataset.col = String(j);
            let num = mat[i][j];
            if (num === 0)
                td.classList.add('space');
            else
                td.textContent = String(num);
            tr.appendChild(td);
        }
        boardElem.appendChild(tr);
    }
}


function init_all() {
    if (difficulty_control.value === 'easy')
        random_mat(2 * (n_rows + n_cols));
    else if (difficulty_control.value === 'medium')
        random_mat(2 * n_rows * n_cols);
    else if (difficulty_control.value === 'hard'){
        board = completely_random_board();
        init_mat();
        init_pos();
    }
    draw();
    reset_state();
    save_state();
}


function init_mat() {
    mat = [];
    for (let i = 0; i < n_rows; i++) {
        mat.push([]);
        for (let j = 0; j < n_cols; j++)
            mat[i][j] = board[i * n_cols + j];
    }
}

function init_pos() {
    where = [];
    for (let i = 0; i < n_rows; i++)
        for (let j = 0; j < n_cols; j++)
            where[mat[i][j]] = [i, j];
}

function slide(matrix, where, dr, dc) {
    // 沿水平/竖直方向移动滑块
    // 记录移动方向和步数
    let [r0, c0] = where[0];
    if (dr !== 0) {
        let sign = dr > 0 ? 1 : -1;
        for (let r = r0; r - r0 !== dr; r += sign) {
            where[matrix[r + sign][c0]] = [r, c0];
            matrix[r][c0] = matrix[r + sign][c0];
        }
    } else if (dc !== 0) {
        let sign = dc > 0 ? 1 : -1;
        for (let c = c0; c - c0 !== dc; c += sign) {
            where[matrix[r0][c + sign]] = [r0, c];
            matrix[r0][c] = matrix[r0][c + sign];
        }
    }
    where[0] = [r0 + dr, c0 + dc];
    matrix[r0 + dr][c0 + dc] = 0;
}

// 滑动显示函数
function slide_display(dr, dc) {
    // 获取空格位置
    let [r0, c0] = where[0];

    if (dr !== 0) {
        // 竖直方向滑动
        let sign = dr > 0 ? 1 : -1;
        for (let r = r0; r !== r0 + dr; r += sign) {
            let fromCell = boardElem.rows[r + sign].cells[c0];
            let toCell = boardElem.rows[r].cells[c0];
            toCell.textContent = fromCell.textContent;
            toCell.classList.remove('space');
            fromCell.classList.add('space');
            fromCell.textContent = '';
        }
    } else if (dc !== 0) {
        // 水平方向滑动
        let sign = dc > 0 ? 1 : -1;
        for (let c = c0; c !== c0 + dc; c += sign) {
            let fromCell = boardElem.rows[r0].cells[c + sign];
            let toCell = boardElem.rows[r0].cells[c];
            toCell.textContent = fromCell.textContent;
            toCell.classList.remove('space');
            fromCell.classList.add('space');
            fromCell.textContent = '';
        }
    }
    // 步数和累计滑块数统计
    stepCount++;
    blockCount += Math.abs(dr) + Math.abs(dc);
    stepCountElem.textContent = stepCount;
    blockCountElem.textContent = blockCount;
}

let stepCount = 0;
let blockCount = 0;
let timer = 0;
let timerInterval = null;
let steps = [[0, 0]];

const stepCountElem = document.getElementById('step-count');
const blockCountElem = document.getElementById('block-count');
const timerElem = document.getElementById('timer');


function reset_state() {
    stepCount = 0;
    blockCount = 0;
    timer = 0;
    stepCountElem.textContent = '0';
    blockCountElem.textContent = '0';
    timerElem.textContent = '0:00';
    if (timerInterval) {
        clearInterval(timerInterval);
        timerInterval = null;
    }
    steps = [[0, 0]];
}

function startTimer() {
    timerInterval = setInterval(() => {
        timer++;
        let min = Math.floor(timer / 60);
        let sec = timer % 60;
        timerElem.textContent = `${min}:${sec.toString().padStart(2, '0')}`;
    }, 1000);
}

function stopTimer() {
    if (timerInterval) {
        clearInterval(timerInterval);
        timerInterval = null;
    }
}

function check_win() {
    board = mat.flat();
    let win_flag = true;
    for (let i = 0; i < board.length - 1; i++)
        if (board[i] !== i + 1) {
            win_flag = false;
            break;
        }
    if (board[board.length-1] !== 0)
        return false;
    return win_flag;
}


function* general_solve() {
    // 通解算法
    let ready_flag = [];
    const gold_op0_index = [0, 2, 1, 3, 1, 2, 0, 0, 3, 1];  // 2×n 拼图黄金操作
    const gold_op1_index = gold_op0_index.map(i => [3, 2, 0, 1][i]);  // 顺时针旋转90度
    const gold_op0 = gold_op0_index.map(i => directions[i])
    const gold_op1 = gold_op1_index.map(i => directions[i])
    // console.log(gold_op1);

    let _mat = mat.map(row => row.slice());  // 深拷贝
    let _where = where.slice();
    
    for (let i = 0; i < n_rows; i++)
        ready_flag.push(new Array(n_cols).fill(0));
    // console.log(ready_flag);

    function find_path(start, end, no_pass = [-1, -1]) {
        let [r, c] = start;
        let [end_r, end_c] = end;
        let [no_r, no_c] = no_pass;
        let flag0 = no_c !== end_c || no_r < Math.min(r, end_r) || no_r > Math.max(r, end_r);
        let flag1 = no_r !== end_r || no_c < Math.min(c, end_c) || no_c > Math.max(c, end_c);
        if (c !== end_c) {
            if (r < end_r) {
                if (flag1)                    return [[end_r - r, 0], [0, end_c - c]];
                if (!ready_flag[r][end_c])    return [[0, end_c - c], [end_r - r, 0]];
                if (end_r === n_rows - 1)     return [[end_r - 1 - r, 0], [0, end_c - c], [1, 0]];
                if (c === no_c)               return [[0, 1], [end_r + 1 - r, 0], [0, end_c - (c + 1)], [-1, 0]];
                return [[end_r + 1 - r, 0], [0, end_c - c], [-1, 0]];
            }
            if (r > end_r) {
                if (flag0)                    return [[0, end_c - c], [end_r - r, 0]];
                if (!ready_flag[end_r][c])    return [[end_r - r, 0], [0, end_c - c]];
                if (r === no_r)               return [[1, 0], [0, end_c + 1 - c], [end_r - (r + 1), 0], [0, -1]];
                return [[0, end_c + 1 - c], [end_r - r, 0], [0, -1]];
            }
            if (r === end_r) {
                if (flag1)             return [[0, end_c - c]];
                if (r === n_rows - 1)  return [[-1, 0], [0, end_c - c], [1, 0]];
                return [[1, 0], [0, end_c - c], [-1, 0]];
            }
        }
        if (c === end_c) {
            if (flag0)             return [[end_r - r, 0]];
            if (c === n_cols - 1)  return [[0, -1], [end_r - r, 0], [0, 1]];
            return [[0, 1], [end_r - r, 0], [0, -1]];
        }
        return [];
    }

    function move_space(target, no_pass) {
        let path = find_path(_where[0], target, no_pass);
        // console.log('path: ', path);
        for (let [dr, dc] of path) {
            slide(_mat, _where, dr, dc);
            console.log(_mat.map(row => row.slice()));
        }
        return path;
    }

    function move(start, end) {  // 移动滑块
        let op_list = [];
        let [now_r, now_c] = start;  // 要移动滑块的位置
        let path = find_path(start, end);
        for (let [dr, dc] of path) {
            // console.log('dr, dc:', dr, dc);
            let sign_dr = dr !== 0 ? dr / Math.abs(dr) : 0;
            let sign_dc = dc !== 0 ? dc / Math.abs(dc) : 0;
            for (let _ = 0; _ < Math.abs(dr); _++) {
                op_list.push(...move_space([now_r + sign_dr, now_c], [now_r, now_c]));
                now_r += sign_dr;
                slide(_mat, _where, -sign_dr, 0);
                console.log(_mat.map(row => row.slice()));
                op_list.push([-sign_dr, 0]);
            }
            for (let _ = 0; _ < Math.abs(dc); _++) {
                op_list.push(...move_space([now_r, now_c + sign_dc], [now_r, now_c]));
                now_c += sign_dc;
                slide(_mat, _where, 0, -sign_dc);
                console.log(_mat.map(row => row.slice()));
                op_list.push([0, -sign_dc]);
            }
        }
        return op_list;
    }

    function do_op(op_list) {
        for (let [dr, dc] of op_list)
            slide(_mat, _where, -dr, -dc);
    }

    function where_is(x, y) {
        let target = x * n_cols + y + 1;
        return _where[target];
    }

    // 核心求解算法
    // 左上部分：n_rows-2行，n_cols-2列
    for (let i = 0; i < n_rows - 2; i++)
        for (let j = 0; j < n_cols - 2; j++) {
            yield* move(where_is(i, j), [i, j]);
            ready_flag[i][j] = 1;
            // console.log(i, j);
        }
    // console.log(JSON.stringify(_mat));

    // 最后两行
    for (let i = 0; i < n_cols - 2; i++) {
        yield* move(where_is(n_rows - 1, i), [n_rows - 1, i]);
        if (_where[0][0] === n_rows - 2 && _where[0][1] === i) {
            slide(_mat, _where, 0, 1);
            yield [0, 1];
        }
        if (where_is(n_rows - 2, i)[0] === n_rows - 2 && where_is(n_rows - 2, i)[1] === i)
            continue;
        yield* move(where_is(n_rows - 2, i), [n_rows - 2, i + 2]);
        yield* move_space([n_rows - 2, i + 1], [n_rows - 2, i + 2]);
        do_op(gold_op0);
        yield* gold_op0.map(([dr, dc]) => [-dr, -dc]);
    }

    // 最后两列
    for (let i = 0; i < n_rows - 2; i++) {
        yield* move(where_is(i, n_cols - 2), [i, n_cols - 2]);
        if (_where[0][0] === i && _where[0][1] === n_cols - 1) {
            slide(_mat, _where, 1, 0);
            yield [1, 0];
        }
        if (where_is(i, n_cols - 1)[0] === i && where_is(i, n_cols - 1)[1] === n_cols - 1)
            continue;
        yield* move(where_is(i, n_cols - 1), [i + 2, n_cols - 1]);
        yield* move_space([i + 1, n_cols - 1], [i + 2, n_cols - 1]);
        do_op(gold_op1);
        yield* gold_op1.map(([dr, dc]) => [-dr, -dc]);
    }

    // 最后还有右下角2*2小正方形
    yield* move(where_is(n_rows - 2, n_cols - 2), [n_rows - 2, n_cols - 2]);
    yield* move(where_is(n_rows - 2, n_cols - 1), [n_rows - 2, n_cols - 1]);
    yield* move(where_is(n_rows - 1, n_cols - 2), [n_rows - 1, n_cols - 2]);

    console.log(_mat.map(row => row.slice()));
}

let initial_board = [];
let initial_mat = [];

function save_state() {
    initial_board = board.slice();
    initial_mat = mat.map(row => row.slice());
}

function restore_state() {
    board = initial_board.slice();
    mat = initial_mat.map(row => row.slice());
    init_pos();
    draw();
    reset_state();
    startTimer();
    gameHeader.style.display = 'none';
}

n_rows_control.addEventListener('change', () => {
    n_rows = Math.floor(n_rows_control.value);
    n_cols = Math.floor(n_cols_control.value);
    if (n_rows > 150)
        n_rows = n_rows_control.value = 150;
    else if (n_rows < 2)
        n_rows = n_rows_control.value = 2;
    else if (n_rows === 2 && n_cols === 2)
        n_rows = n_rows_control.value = 3;
    else n_rows = n_rows_control.value = Math.floor(n_rows);
})

n_cols_control.addEventListener('change', () => {
    n_rows = Math.floor(n_rows_control.value);
    n_cols = Math.floor(n_cols_control.value);
    if (n_cols > 150)
        n_cols = n_cols_control.value = 150;
    else if (n_cols < 2)
        n_cols = n_cols_control.value = 2;
    else if (n_rows === 2 && n_cols === 2)
        n_cols = n_cols_control.value = 3;
    else n_cols = n_cols_control.value = Math.floor(n_cols);
})

init_all();
startTimer();

btn_random.addEventListener('click', () => {
    init_all();
    startTimer();
    auto = false;
    gameHeader.style.display = 'none';
})

boardElem.addEventListener('click', (e) => {
    let clickedCell = e.target;
    // console.log(clickedCell);
    let clickedRow = Number(clickedCell.dataset.row);
    let clickedCol = Number(clickedCell.dataset.col);
    if ((clickedRow === where[0][0]) ^ (clickedCol === where[0][1])) {
        let dr = clickedRow - where[0][0];
        let dc = clickedCol - where[0][1];
        slide_display(dr, dc);
        slide(mat, where, dr, dc);
    }
    if (!auto && check_win()) {
        gameHeader.style.display = 'flex';
        gameHeader.textContent = '恭喜你完成拼图！';
        stopTimer();
    }
})


btn_replay.addEventListener('click', () => {
    restore_state();
    auto = false;
});


let gen;


btn_solve.addEventListener('click', () => {
    stopTimer();
    timerElem.textContent = '-:--';
    gen = general_solve();
    gameHeader.style.display = 'flex';
    auto = true;
})

function next_step() {
    while (true) {
        let next = gen.next();
        let last = steps[steps.length - 1];
        if (next.done) {
            gameHeader.style.display = 'none';
            slide_display(...last);
            slide(mat, where, ...last);
            break;
        }
        if ((last[0] === next.value[0] && last[0] === 0) || (last[1] === next.value[1] && last[1] === 0)) {
            last[0] += next.value[0];
            last[1] += next.value[1];
        } else {
            console.log(last);
            slide_display(...last);
            slide(mat, where, ...last);
            steps.push(next.value);
            break
        }
    }
}

btn_next.addEventListener('click', next_step);
